//
//  huffman.cpp
//  word2vec
//
//  Created by LazyLie on 14-8-11.
//  Copyright (c) 2014年 NLP Group. All rights reserved.
//

#include "huffman.h"
#include <algorithm>
#include <iostream>

void huffman::init(const std::vector<std::pair<int, int> > &counter) {
    leaf.resize(counter.size(), std::make_pair(-1, 0));
    node.resize(counter.size() - 1, std::make_pair(-1, 0));
    int p1 = 0, p2 = 0;
    std::vector< std::pair<int,int> > tmp;
    for (int i = 0; i < counter.size() - 1; i++) {
        int sum = 0;
        for (int j = 0; j < 2; j++) {
            if (p2 == tmp.size() || (p1 != counter.size() && counter[p1].first < tmp[p2].first)) {
                sum += counter[p1].first;
                leaf[counter[p1].second] = std::make_pair(i, j);
                p1++;
            } else {
                sum += tmp[p2].first;
                node[tmp[p2].second] = std::make_pair(i, j);
                p2++;
            }
        }
        tmp.push_back(std::make_pair(sum, i));
    }
    if (p1 != counter.size() || p2 != tmp.size() - 1) {
        std::cout << "Fail: huffman" << std::endl;
        exit(0);
    }
}

huffman::route_t huffman::get_route(int id) {
    route_t route;
    route.push_back(leaf[id]);
    id = leaf[id].first;
    while (node[id].first != -1) {
        route.push_back(node[id]);
        id = node[id].first;
    }
    return route;
}